home *** CD-ROM | disk | FTP | other *** search
/ Over 1,000 Windows 95 Programs / Over 1000 Windows 95 Programs (Microforum) (Disc 1).iso / 1249 / dijkstra.t < prev    next >
Encoding:
Text File  |  1997-04-18  |  3.5 KB  |  196 lines
  1. %
  2. % "dijkstra.t" finds shortest path in a network by
  3. % using Dijksta's algorithm
  4. %
  5. %   Sample program for the T Interpreter by:
  6. %
  7. %   Stephen R. Schmitt
  8. %   962 Depot Road
  9. %   Boxborough, MA 01719
  10. %
  11.  
  12. const N : int := 7
  13. const Infinity : int := 2147483647
  14. var G : array[N+1,N+1] of int
  15.  
  16. type mark : enum[ temporary, permanent ]
  17.  
  18. type vertex : record
  19.  
  20.                 prev : int
  21.                 lnth : int
  22.                 labl : mark
  23.  
  24.               end record
  25.  
  26. var P : array[N+1] of vertex
  27.  
  28. program
  29.  
  30.     var i, j, lnth, p : int
  31.  
  32.     % step one
  33.  
  34.     init_table
  35.  
  36.     P[1].prev := 1
  37.     P[1].lnth := 0              % starting node is labeled with 0
  38.     P[1].labl := mark.permanent % starting node is permanently labeled
  39.     
  40.     for i := 2...N do
  41.     
  42.         P[i].prev := 1
  43.         P[i].lnth := G[1,i]
  44.         P[i].labl := mark.temporary
  45.  
  46.     end for
  47.  
  48.     loop
  49.  
  50.         % step two
  51.  
  52.         p := 0
  53.         lnth := Infinity
  54.  
  55.         for i := 2...N do
  56.  
  57.             if P[i].labl = mark.temporary then
  58.  
  59.                 if P[i].lnth < lnth then
  60.  
  61.                     p := i
  62.                     lnth := P[i].lnth
  63.  
  64.                 end if
  65.  
  66.             end if
  67.  
  68.         end for
  69.  
  70.         exit when p = 0
  71.  
  72.         P[p].labl := mark.permanent
  73.  
  74.         % step three
  75.  
  76.         for i := 2...N do
  77.  
  78.             if P[i].labl = mark.temporary then
  79.  
  80.                 for j := 2...N do
  81.  
  82.                     if P[j].lnth = Infinity or G[j,i] = Infinity then
  83.  
  84.                         lnth := Infinity
  85.  
  86.                     else
  87.  
  88.                         lnth := P[j].lnth + G[j,i]
  89.  
  90.                     end if
  91.  
  92.                     if P[i].lnth > lnth then
  93.  
  94.                         P[i].lnth := lnth
  95.                         P[i].prev := j
  96.  
  97.                     end if
  98.  
  99.                 end for
  100.  
  101.             end if
  102.  
  103.         end for
  104.  
  105.     end loop
  106.  
  107.     % show resulting paths
  108.  
  109.     for i := 1...N do
  110.  
  111.         put "path from ", i, " to 1 has length of ", P[i].lnth
  112.  
  113.         j := i
  114.  
  115.         loop
  116.  
  117.             put j
  118.             exit when j = 1
  119.             j := P[j].prev
  120.  
  121.         end loop
  122.  
  123.     end for
  124.         
  125. end program
  126.  
  127. %
  128. % to:       1   2   3   4   5   6   7
  129. % -------------------------------------
  130. %       1|  0   #   #   #   1   4   #
  131. %       2|  #   0   #   #  10   2   3
  132. %       3|  #   #   0   #   7   6   5
  133. % from: 4|  #   #   #   0   #   8   7
  134. %       5|  1  10   7   #   0   #   #
  135. %       6|  4   2   6   8   #   0   #
  136. %       7|  #   3   5   7   #   #   0
  137. %
  138. procedure init_table
  139.     
  140.     G[1,1] := 0
  141.     G[1,2] := Infinity
  142.     G[1,3] := Infinity
  143.     G[1,4] := Infinity
  144.     G[1,5] := 1
  145.     G[1,6] := 4
  146.     G[1,7] := Infinity
  147.  
  148.     G[2,1] := Infinity
  149.     G[2,2] := 0
  150.     G[2,3] := Infinity
  151.     G[2,4] := Infinity
  152.     G[2,5] := 10
  153.     G[2,6] := 2
  154.     G[2,7] := 3
  155.  
  156.     G[3,1] := Infinity
  157.     G[3,2] := Infinity
  158.     G[3,3] := 0
  159.     G[3,4] := Infinity
  160.     G[3,5] := 7
  161.     G[3,6] := 6
  162.     G[3,7] := 5
  163.     
  164.     G[4,1] := Infinity
  165.     G[4,2] := Infinity
  166.     G[4,3] := Infinity
  167.     G[4,4] := 0
  168.     G[4,5] := Infinity
  169.     G[4,6] := 8
  170.     G[4,7] := 7
  171.  
  172.     G[5,1] := 1
  173.     G[5,2] := 10
  174.     G[5,3] := 7
  175.     G[5,4] := Infinity
  176.     G[5,5] := 0
  177.     G[5,6] := Infinity
  178.     G[5,7] := Infinity
  179.  
  180.     G[6,1] := 4
  181.     G[6,2] := 2
  182.     G[6,3] := 6
  183.     G[6,4] := 8
  184.     G[6,5] := Infinity
  185.     G[6,6] := 0
  186.     G[6,7] := Infinity
  187.  
  188.     G[7,1] := Infinity
  189.     G[7,2] := 3
  190.     G[7,3] := 5
  191.     G[7,4] := 7
  192.     G[7,5] := Infinity
  193.     G[7,6] := Infinity
  194.     G[7,7] := 0
  195.  
  196. end procedure